home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / grep / grep.lzh / regex.c < prev    next >
C/C++ Source or Header  |  1989-03-02  |  45KB  |  1,737 lines
  1. /* Extended regular expression matching and search library.
  2.    Copyright (C) 1985, 1989 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 1, or (at your option)
  7.    any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17.  
  18.  
  19.    In other words, you are welcome to use, share and improve this program.
  20.    You are forbidden to forbid anyone else to use, share and improve
  21.    what you give them.   Help stamp out software-hoarding!  */
  22.  
  23.  
  24. /* To test, compile with -Dtest.
  25.  This Dtestable feature turns this into a self-contained program
  26.  which reads a pattern, describes how it compiles,
  27.  then reads a string and searches for it.  */
  28.  
  29. #ifdef emacs
  30.  
  31. /* The `emacs' switch turns on certain special matching commands
  32.  that make sense only in emacs. */
  33.  
  34. #include "config.h"
  35. #include "lisp.h"
  36. #include "buffer.h"
  37. #include "syntax.h"
  38.  
  39. #else  /* not emacs */
  40.  
  41. #ifdef USG
  42. #define bcopy(s,d,n)    memcpy((d),(s),(n))
  43. #define bcmp(s1,s2,n)    memcmp((s1),(s2),(n))
  44. #define bzero(s,n)    memset((s),0,(n))
  45. #endif
  46.  
  47. /* Make alloca work the best possible way.  */
  48. #ifdef __GNUC__
  49. #define alloca __builtin_alloca
  50. #else
  51. #ifdef sparc
  52. #include <alloca.h>
  53. #endif
  54. #endif
  55.  
  56. /*
  57.  * Define the syntax stuff, so we can do the \<...\> things.
  58.  */
  59.  
  60. #ifndef Sword /* must be non-zero in some of the tests below... */
  61. #define Sword 1
  62. #endif
  63.  
  64. #define SYNTAX(c) re_syntax_table[c]
  65.  
  66. #ifdef SYNTAX_TABLE
  67.  
  68. char *re_syntax_table;
  69.  
  70. #else
  71.  
  72. static char re_syntax_table[256];
  73.  
  74. static void
  75. init_syntax_once ()
  76. {
  77.    register int c;
  78.    static int done = 0;
  79.  
  80.    if (done)
  81.      return;
  82.  
  83.    bzero (re_syntax_table, sizeof re_syntax_table);
  84.  
  85.    for (c = 'a'; c <= 'z'; c++)
  86.      re_syntax_table[c] = Sword;
  87.  
  88.    for (c = 'A'; c <= 'Z'; c++)
  89.      re_syntax_table[c] = Sword;
  90.  
  91.    for (c = '0'; c <= '9'; c++)
  92.      re_syntax_table[c] = Sword;
  93.  
  94.    done = 1;
  95. }
  96.  
  97. #endif /* SYNTAX_TABLE */
  98. #endif /* not emacs */
  99.  
  100. #include "regex.h"
  101.  
  102. /* Number of failure points to allocate space for initially,
  103.  when matching.  If this number is exceeded, more space is allocated,
  104.  so it is not a hard limit.  */
  105.  
  106. #ifndef NFAILURES
  107. #define NFAILURES 80
  108. #endif /* NFAILURES */
  109.  
  110. /* width of a byte in bits */
  111.  
  112. #define BYTEWIDTH 8
  113.  
  114. #ifndef SIGN_EXTEND_CHAR
  115. #define SIGN_EXTEND_CHAR(x) (x)
  116. #endif
  117.  
  118. static int obscure_syntax = 0;
  119.  
  120. /* Specify the precise syntax of regexp for compilation.
  121.    This provides for compatibility for various utilities
  122.    which historically have different, incompatible syntaxes.
  123.  
  124.    The argument SYNTAX is a bit-mask containing the two bits
  125.    RE_NO_BK_PARENS and RE_NO_BK_VBAR.  */
  126.  
  127. int
  128. re_set_syntax (syntax)
  129. {
  130.   int ret;
  131.  
  132.   ret = obscure_syntax;
  133.   obscure_syntax = syntax;
  134.   return ret;
  135. }
  136.  
  137. /* re_compile_pattern takes a regular-expression string
  138.    and converts it into a buffer full of byte commands for matching.
  139.  
  140.   PATTERN   is the address of the pattern string
  141.   SIZE      is the length of it.
  142.   BUFP        is a  struct re_pattern_buffer *  which points to the info
  143.         on where to store the byte commands.
  144.         This structure contains a  char *  which points to the
  145.         actual space, which should have been obtained with malloc.
  146.         re_compile_pattern may use  realloc  to grow the buffer space.
  147.  
  148.   The number of bytes of commands can be found out by looking in
  149.   the  struct re_pattern_buffer  that bufp pointed to,
  150.   after re_compile_pattern returns.
  151. */
  152.  
  153. #define PATPUSH(ch) (*b++ = (char) (ch))
  154.  
  155. #define PATFETCH(c) \
  156.  {if (p == pend) goto end_of_pattern; \
  157.   c = * (unsigned char *) p++; \
  158.   if (translate) c = translate[c]; }
  159.  
  160. #define PATFETCH_RAW(c) \
  161.  {if (p == pend) goto end_of_pattern; \
  162.   c = * (unsigned char *) p++; }
  163.  
  164. #define PATUNFETCH p--
  165.  
  166. #define EXTEND_BUFFER \
  167.   { char *old_buffer = bufp->buffer; \
  168.     if (bufp->allocated == (1<<16)) goto too_big; \
  169.     bufp->allocated *= 2; \
  170.     if (bufp->allocated > (1<<16)) bufp->allocated = (1<<16); \
  171.     if (!(bufp->buffer = (char *) realloc (bufp->buffer, bufp->allocated))) \
  172.       goto memory_exhausted; \
  173.     c = bufp->buffer - old_buffer; \
  174.     b += c; \
  175.     if (fixup_jump) \
  176.       fixup_jump += c; \
  177.     if (laststart) \
  178.       laststart += c; \
  179.     begalt += c; \
  180.     if (pending_exact) \
  181.       pending_exact += c; \
  182.   }
  183.  
  184. static int store_jump (), insert_jump ();
  185.  
  186. char *
  187. re_compile_pattern (pattern, size, bufp)
  188.      char *pattern;
  189.      int size;
  190.      struct re_pattern_buffer *bufp;
  191. {
  192.   register char *b = bufp->buffer;
  193.   register char *p = pattern;
  194.   char *pend = pattern + size;
  195.   register unsigned c, c1;
  196.   char *p1;
  197.   unsigned char *translate = (unsigned char *) bufp->translate;
  198.  
  199.   /* address of the count-byte of the most recently inserted "exactn" command.
  200.     This makes it possible to tell whether a new exact-match character
  201.     can be added to that command or requires a new "exactn" command. */
  202.      
  203.   char *pending_exact = 0;
  204.  
  205.   /* address of the place where a forward-jump should go
  206.     to the end of the containing expression.
  207.     Each alternative of an "or", except the last, ends with a forward-jump
  208.     of this sort. */
  209.  
  210.   char *fixup_jump = 0;
  211.  
  212.   /* address of start of the most recently finished expression.
  213.     This tells postfix * where to find the start of its operand. */
  214.  
  215.   char *laststart = 0;
  216.  
  217.   /* In processing a repeat, 1 means zero matches is allowed */
  218.  
  219.   char zero_times_ok;
  220.  
  221.   /* In processing a repeat, 1 means many matches is allowed */
  222.  
  223.   char many_times_ok;
  224.  
  225.   /* address of beginning of regexp, or inside of last \( */
  226.  
  227.   char *begalt = b;
  228.  
  229.   /* Stack of information saved by \( and restored by \).
  230.      Four stack elements are pushed by each \(:
  231.        First, the value of b.
  232.        Second, the value of fixup_jump.
  233.        Third, the value of regnum.
  234.        Fourth, the value of begalt.  */
  235.  
  236.   int stackb[40];
  237.   int *stackp = stackb;
  238.   int *stacke = stackb + 40;
  239.   int *stackt;
  240.  
  241.   /* Counts \('s as they are encountered.  Remembered for the matching \),
  242.      where it becomes the "register number" to put in the stop_memory command */
  243.  
  244.   int regnum = 1;
  245.  
  246.   bufp->fastmap_accurate = 0;
  247.  
  248. #ifndef emacs
  249. #ifndef SYNTAX_TABLE
  250.   /*
  251.    * Initialize the syntax table.
  252.    */
  253.    init_syntax_once();
  254. #endif
  255. #endif
  256.  
  257.   if (bufp->allocated == 0)
  258.     {
  259.       bufp->allocated = 28;
  260.       if (bufp->buffer)
  261.     /* EXTEND_BUFFER loses when bufp->allocated is 0 */
  262.     bufp->buffer = (char *) realloc (bufp->buffer, 28);
  263.       else
  264.     /* Caller did not allocate a buffer.  Do it for him */
  265.     bufp->buffer = (char *) malloc (28);
  266.       if (!bufp->buffer) goto memory_exhausted;
  267.       begalt = b = bufp->buffer;
  268.     }
  269.  
  270.   while (p != pend)
  271.     {
  272.       if (b - bufp->buffer > bufp->allocated - 10)
  273.     /* Note that EXTEND_BUFFER clobbers c */
  274.     EXTEND_BUFFER;
  275.  
  276.       PATFETCH (c);
  277.  
  278.       switch (c)
  279.     {
  280.     case '$':
  281.       if (obscure_syntax & RE_TIGHT_VBAR)
  282.         {
  283.           if (! (obscure_syntax & RE_CONTEXT_INDEP_OPS) && p != pend)
  284.         goto normal_char;
  285.           /* Make operand of last vbar end before this `$'.  */
  286.           if (fixup_jump)
  287.         store_jump (fixup_jump, jump, b);
  288.           fixup_jump = 0;
  289.           PATPUSH (endline);
  290.           break;
  291.         }
  292.  
  293.       /* $ means succeed if at end of line, but only in special contexts.
  294.         If randomly in the middle of a pattern, it is a normal character. */
  295.       if (p == pend || *p == '\n'
  296.           || (obscure_syntax & RE_CONTEXT_INDEP_OPS)
  297.           || (obscure_syntax & RE_NO_BK_PARENS
  298.           ? *p == ')'
  299.           : *p == '\\' && p[1] == ')')
  300.           || (obscure_syntax & RE_NO_BK_VBAR
  301.           ? *p == '|'
  302.           : *p == '\\' && p[1] == '|'))
  303.         {
  304.           PATPUSH (endline);
  305.           break;
  306.         }
  307.       goto normal_char;
  308.  
  309.     case '^':
  310.       /* ^ means succeed if at beg of line, but only if no preceding pattern. */
  311.  
  312.       if (laststart && p[-2] != '\n'
  313.           && ! (obscure_syntax & RE_CONTEXT_IND